.TH std::ranges::lower_bound 3 "2024.06.10" "http://cppreference.com" "C++ Standard Libary"
.SH NAME
std::ranges::lower_bound \- std::ranges::lower_bound

.SH Synopsis
   Defined in header <algorithm>
   Call signature
   template< std::forward_iterator I, std::sentinel_for<I> S,

             class T, class Proj = std::identity,                       (since
             std::indirect_strict_weak_order                            C++20)
                 <const T*, std::projected<I, Proj>> Comp =             (until
   ranges::less >                                                       C++26)
   constexpr I lower_bound( I first, S last, const T& value,

                            Comp comp = {}, Proj proj = {} );
   template< std::forward_iterator I, std::sentinel_for<I> S,

             class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>,
             std::indirect_strict_weak_order                            (since
                 <const T*, std::projected<I, Proj>> Comp =             C++26)
   ranges::less >
   constexpr I lower_bound( I first, S last, const T& value,

                            Comp comp = {}, Proj proj = {} );
   template< ranges::forward_range R,

             class T, class Proj = std::identity,
             std::indirect_strict_weak_order                    \fB(1)\fP
                 <const T*,                                                     (since
   std::projected<ranges::iterator_t<R>,                                        C++20)
                                           Proj>> Comp =                        (until
   ranges::less >                                                               C++26)
   constexpr ranges::borrowed_iterator_t<R>

       lower_bound( R&& r, const T& value, Comp comp = {}, Proj
   proj = {} );
   template< ranges::forward_range R,                               \fB(2)\fP

             class Proj = std::identity,
             class T =
   std::projected_value_t<ranges::iterator_t<R>, Proj>
             std::indirect_strict_weak_order
                 <const T*,                                                     (since
   std::projected<ranges::iterator_t<R>,                                        C++26)
                                           Proj>> Comp =
   ranges::less >
   constexpr ranges::borrowed_iterator_t<R>

       lower_bound( R&& r, const T& value, Comp comp = {}, Proj
   proj = {} );

   1) Returns an iterator pointing to the first element in the range [first, last) that
   is not less than (i.e. greater or equal to) value, or last if no such element is
   found. The range [first, last) must be partitioned with respect to the expression
   std::invoke(comp, std::invoke(proj, element), value), i.e., all elements for which
   the expression is true must precede all elements for which the expression is false.
   A fully-sorted range meets this criterion.
   2) Same as \fB(1)\fP, but uses r as the source range, as if using ranges::begin(r) as
   first and ranges::end(r) as last.

   The function-like entities described on this page are niebloids, that is:

     * Explicit template argument lists cannot be specified when calling any of them.
     * None of them are visible to argument-dependent lookup.
     * When any of them are found by normal unqualified lookup as the name to the left
       of the function-call operator, argument-dependent lookup is inhibited.

   In practice, they may be implemented as function objects, or with special compiler
   extensions.

.SH Parameters

   first, last - iterator-sentinel pair defining the partially-ordered range to examine
   r           - the partially-ordered range to examine
   value       - value to compare the projected elements to
   comp        - comparison predicate to apply to the projected elements
   proj        - projection to apply to the elements

.SH Return value

   Iterator pointing to the first element that is not less than value, or last if no
   such element is found.

.SH Complexity

   The number of comparisons and applications of the projection performed are
   logarithmic in the distance between first and last (at most log
   2(last - first) + O(1) comparisons and applications of the projection). However, for
   an iterator that does not model random_access_iterator, the number of iterator
   increments is linear.

.SH Notes

   On a range that's fully sorted (or more generally, partially ordered with respect to
   value) after projection, std::ranges::lower_bound implements the binary search
   algorithm. Therefore, std::ranges::binary_search can be implemented in terms of it.

             Feature-test macro           Value    Std              Feature
   __cpp_lib_algorithm_default_value_type 202403 (C++26) List-initialization for
                                                         algorithms (1,2)

.SH Possible implementation

 struct lower_bound_fn
 {
     template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
              class T = std::projected_value_t<I, Proj>,
              std::indirect_strict_weak_order
                  <const T*, std::projected<I, Proj>> Comp = ranges::less>
     constexpr I operator()(I first, S last, const T& value,
                            Comp comp = {}, Proj proj = {}) const
     {
         I it;
         std::iter_difference_t<I> count, step;
         count = std::ranges::distance(first, last);

         while (count > 0)
         {
             it = first;
             step = count / 2;
             ranges::advance(it, step, last);
             if (comp(std::invoke(proj, *it), value))
             {
                 first = ++it;
                 count -= step + 1;
             }
             else
                 count = step;
         }
         return first;
     }

     template<ranges::forward_range R, class Proj = std::identity,
           class T = std::projected_value_t<ranges::iterator_t<R>, Proj>
           std::indirect_strict_weak_order
               <const T*, std::projected<ranges::iterator_t<R>,
                                         Proj>> Comp = ranges::less>
     constexpr ranges::borrowed_iterator_t<R>
         operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
     {
         return (*this)(ranges::begin(r), ranges::end(r), value,
                        std::ref(comp), std::ref(proj));
     }
 };

 inline constexpr lower_bound_fn lower_bound;

.SH Example


// Run this code

 #include <algorithm>
 #include <cassert>
 #include <complex>
 #include <iostream>
 #include <iterator>
 #include <vector>

 namespace ranges = std::ranges;

 template<std::forward_iterator I, std::sentinel_for<I> S, class T,
          class Proj = std::identity,
          std::indirect_strict_weak_order
              <const T*, std::projected<I, Proj>> Comp = ranges::less>
 constexpr I binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
 {
     first = ranges::lower_bound(first, last, value, comp, proj);
     return first != last && !comp(value, proj(*first)) ? first : last;
 }

 int main()
 {
     std::vector data{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
     //                                 ^^^^^^^^^^
     auto lower = ranges::lower_bound(data, 4);
     auto upper = ranges::upper_bound(data, 4);

     std::cout << "found a range [" << ranges::distance(data.cbegin(), lower)
               << ", " << ranges::distance(data.cbegin(), upper) << ") = { ";
     ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
     std::cout << "}\\n";

     // classic binary search, returning a value only if it is present

     data = {1, 2, 4, 8, 16};
     //               ^
     auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' would return end()

     if (it != data.cend())
         std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it);

     using CD = std::complex<double>;
     std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}};
     auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
     #ifdef __cpp_lib_algorithm_default_value_type
         auto it2 = ranges::lower_bound(nums, {2, 0}, cmpz);
     #else
         auto it2 = ranges::lower_bound(nums, CD{2, 0}, cmpz);
     #endif
     assert((*it2 == CD{2, 2}));
 }

.SH Output:

 found a range [6, 10) = { 4 4 4 4 }
 8 found at index 3

.SH See also

   ranges::equal_range     returns range of elements matching a specific key
   (C++20)                 (niebloid)
   ranges::partition       divides a range of elements into two groups
   (C++20)                 (niebloid)
   ranges::partition_point locates the partition point of a partitioned range
   (C++20)                 (niebloid)
   ranges::upper_bound     returns an iterator to the first element greater than a
   (C++20)                 certain value
                           (niebloid)
                           returns an iterator to the first element not less than the
   lower_bound             given value
                           \fI(function template)\fP
